package leetcode.heap.offer.p40;

import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 
 * @Title: Solution40.java 
 * @Package leetcode.offer.p40 
 * @Description: 剑指 Offer 40. 最小的k个数
 *                  使用jdk自带的基于最大堆的优先级队列
 * @author CandyWall   
 * @date 2021年1月9日 上午11:02:34 
 * @version V1.0
 */
public class Solution40_v2 { 
    public int[] getLeastNumbers(int[] arr, int k) {
        // 构建基于最大堆的优先队列，jdk默认的优先级队列是最小堆，因此需要传入比较器，
        /*PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(o1.compareTo(o2) > 0) {
                    return -1;
                } else if(o1.compareTo(o2) < 0) {
                    return 1;
                }
                return 0;
            }
            
        });*/
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 0; i < k; i++) {
            queue.add(arr[i]);
        }
        for(int i = k; i < arr.length; i++) {
            if(!queue.isEmpty() && arr[i] < queue.peek()) {
                queue.remove();
                queue.add(arr[i]);
            }
        }
        int[] res = new int[k];
        for(int i = 0; i < k; i++) {
            res[i] = queue.remove();
        }
        return res;
    }
}
